eratosten kalburu ne demek?

İşte Eratosten Kalburu hakkında kapsamlı bir makale:

Eratosten Kalburu

Eratosten Kalburu, belirli bir sınıra kadar olan tüm asal sayıları bulmak için kullanılan basit ve eski bir algoritmadır. Adını, MÖ 3. yüzyılda yaşamış Yunan matematikçi Eratosten'den almıştır. Verimli ve anlaşılması kolay olması nedeniyle hala sıklıkla öğretilmektedir.

İçindekiler

  1. Giriş
  2. Tarihçe
  3. Algoritma
  4. Karmaşıklık Analizi
  5. Optimizasyonlar
  6. Uygulamalar
  7. Avantajlar ve Dezavantajlar
  8. Alternatif Algoritmalar
  9. Ayrıca Bakınız
  10. Referanslar

1. Giriş

Eratosten Kalburu, bir aralıktaki asal sayıları bulmanın en basit ve eski yöntemlerinden biridir. Temel prensibi, asal sayı'nın katlarını eleyerek ilerlemektir. Bu işlem, belirli bir sınıra kadar olan tüm asal sayılar belirlenene kadar devam eder.

2. Tarihçe

Algoritma, MÖ 3. yüzyılda yaşamış olan Yunan matematikçi Eratosten tarafından geliştirilmiştir. Eratosten, aynı zamanda Dünya'nın çevresini oldukça doğru bir şekilde hesaplamasıyla da bilinir.

3. Algoritma

Adım Adım Açıklama

  1. Belirli bir n sayısına kadar olan tüm sayıların (2'den n'ye kadar) bir listesini oluşturun.
  2. Listenin ilk sayısı olan 2 ile başlayın (2 bir asal sayı'dır).
  3. 2'nin tüm katlarını (4, 6, 8, ...) listeden eleyin.
  4. Listede işaretlenmemiş bir sonraki sayıya gidin (bu sayı da bir asal sayı'dır).
  5. Bu sayının tüm katlarını listeden eleyin.
  6. Listede işaretlenmemiş bir sonraki sayıya gidin ve 4. ve 5. adımları tekrarlayın.
  7. Listenin sonuna kadar bu işlemi tekrarlayın.
  8. Listenin sonunda kalan işaretlenmemiş sayılar, n'ye kadar olan tüm asal sayılardır.

Sözde Kod

function eratostenKalburu(n) {
    // n boyutunda bir boolean dizisi oluştur (başlangıçta hepsi true)
    asalMi = new boolean[n+1];
    doldur(asalMi, true); // Tüm elemanları true yap
    asalMi[0] = asalMi[1] = false; // 0 ve 1 asal sayı değildir

    for (p = 2; p*p <= n; p++) {
        // Eğer asalMi[p] hala true ise, bu bir asal sayıdır
        if (asalMi[p] == true) {
            // p'nin tüm katlarını işaretle
            for (i = p*p; i <= n; i += p)
                asalMi[i] = false;
        }
    }

    // Tüm asal sayıları yazdır
    for (p = 2; p <= n; p++) {
        if (asalMi[p] == true)
            yazdır(p);
    }
}

4. Karmaşıklık Analizi

Zaman Karmaşıklığı

Eratosten Kalburu'nun zaman karmaşıklığı O(n log log n)'dir. Bu, algoritmanın çok verimli olduğu anlamına gelir. Algoritmanın asal sayıları bulma hızı, aralığın büyüklüğü arttıkça nispeten yavaş bir şekilde artar.

Alan Karmaşıklığı

Eratosten Kalburu'nun alan karmaşıklığı O(n)'dir, çünkü n'ye kadar olan tüm sayılar için bir dizi saklamayı gerektirir.

5. Optimizasyonlar

  • Sadece Tek Sayıları Kontrol Etme: 2'den sonra, tüm çift sayılar asal sayı olamaz. Bu nedenle, 2'den sonra sadece tek sayıları kontrol ederek algoritmayı optimize edebiliriz.
  • Karekök Sınırı: Bir sayının katlarını işaretlemeye, sayının karesinden başlayarak başlayabiliriz (örneğin, 7 için 49'dan başlayarak). Çünkü daha küçük katlar zaten daha küçük asal sayılar tarafından işaretlenmiş olacaktır.

6. Uygulamalar

Eratosten Kalburu çeşitli uygulamalarda kullanılır:

  • Kriptografi: Asal sayılar, kriptografi'de önemli bir rol oynar.
  • Sayı Teorisi: Asal sayılarla ilgili birçok problemde kullanılır.
  • Bilgisayar Bilimi: Çeşitli algoritmaların test edilmesinde ve geliştirilmesinde kullanılır.

7. Avantajlar ve Dezavantajlar

Avantajları

  • Basit ve kolay anlaşılır bir algoritmadır.
  • Verimli bir algoritmadır (O(n log log n) zaman karmaşıklığı).
  • Belirli bir sınıra kadar olan tüm asal sayıları bulmak için etkilidir.

Dezavantajları

  • Büyük n değerleri için hafıza gereksinimi yüksek olabilir (O(n) alan karmaşıklığı).
  • Çok büyük sayılar için diğer algoritmalar daha verimli olabilir.

8. Alternatif Algoritmalar

  • Atkin Kalburu: Eratosten Kalburu'na göre daha karmaşık, ancak bazı durumlarda daha verimli bir alternatiftir.
  • Probabilistic Asallık Testleri: Örneğin, Miller-Rabin Asallık Testi. Bu testler, bir sayının asal sayı olup olmadığını belirli bir olasılıkla belirler.

9. Ayrıca Bakınız

10. Referanslar

  • Crandall, R., & Pomerance, C. (2005). Prime Numbers: A Computational Perspective (2nd ed.). Springer.
  • Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley.

Umarım bu makale Eratosten Kalburu hakkında kapsamlı bilgi sağlamıştır.

Kendi sorunu sor